package com.my.study.algorithm.linked;

/**
 * @author Carlos
 * @version 1.0
 * @Description 描述：
 * <p> 给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
 *  解题思想：
 *  1、使用数学思维，把题目抽象出来成一个数学问题：追逐相遇问题！
 *  2、使用快慢指针
 *
 * </p>
 * @date 2021/11/3 8:23
 **/
public class EntryNodeOfLoop {

    public static void main(String[] args) {



    }



    static ListNode entryNodeOfLoop(ListNode pHead) {
        // 定义快慢指针，让快指针的速度为慢指针的2倍
        ListNode fast = pHead;
        ListNode slow = pHead;

        // 找到第一次相遇的点，如果无环，则直接返回null
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (slow == fast) {
                break;
            }
        }
        // 无环，直接退出
        if (fast == null || fast.next == null) {
            return null;
        }

        // 第一次相遇后，使fast回到头结点并与slow相同速度开始遍历
        // 相遇点就是环的入口
        fast = pHead;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }

        return fast;
    }

}
